A "channel" is the propagating medium or electromagnetic path connecting a transmitter and receiver and may be represented by a transmission line or, more generally, by any device characterized by a relevant alphabet of input signals i, output signals j, and a set of conditional probabilities P (j.vertline.i) that describe the likelihood of receiving a signal j given that i was transmitted. It is useful to adopt the convention that the term binary refers to the alphabet {0,1} while the term bipolar refers to the alphabet {-1, +1}. The bipolar version of a binary sequence will mean the sequence obtained by substituting +1 for the symbol 1 and -1 for the symbol 0. A conventional digital communication system utilizes a channel which gives rise to no intersymbol interference at time multiples of the symbol spacing interval, or which utlizes an equalizer to create this condition. When digital signals are transmitted over a channel at the Nyquist rate interference among the symbols occurs. When this is done in a controlled manner, the channel appears to have "memory" inasmuch as the received signal depends not only on the present symbol but also on a symbol that was transmitted one or two or N symbol intervals ago. The polynomial generally describing such a channel's transfer function may be expressed as G(D)=1.+-.D.+-. . . . .+-.D.sup.N, where D represents one signaling interval of delay.
Where the duration and repetition rate of the signals in relation to the channel bandwidth are such that the amount of interference between successive pulses is within certain limits, a multi-level form of signaling called partial response signaling results. Partial response signaling is used in a variety of applications, including magnetic recording, baseband repeaters for T-carrier, voice-channel modems and digital radio. Partial response signaling is of special interest over a partial response channel whose polynomial transfer function has a (1-D) factor exhibit a spectral null at zero frequency, i.e., the power density function of a channel sequence at zero frequency is zero and is a simple model for channels that cannot pass dc signals, e.g., those involving transformers. Among the dc-free channels used in magnetic recording systems are those characterized by the duobinary partial response (PR class 1) channel whose transfer polynomial is (1-D). The transfer polynomial (1-D) indicates that the channel has a "memory" of the immediately preceding digit. The modified duobinary (PR class 4) channel has a transfer polynomial of (1-D.sup.2), indicating that the channel has a "memory" of the symbol transmitted two time intervals ago. These two partial response channels may be characterized as being "dc-free". When successive bipolar symbols having magnitudes .+-.1 are applied to a channel having a (1-D) transfer function the result is signals having 3 amplitude levels, +2, 0 or -2.
If the sequences of signals applied to the dc-free partial response channel are encoded so that the codes are dc-free, a reduced probability of error in signal transmission is obtained. See, for example, R. Karabed and P. Siegel, "Matched Spectral Null Codes for the 1-D Partial-Response Channel", IEEE Trans. On Info. Theory, Vol, IT-37, No.3, May 1991, pp. 818-855 and U.S. Pat. No. 4,888,779 issued Dec. 19, 1989. The straightforward way of obtaining a dc-free code requires that each code have a block digital sum (BDS) of zero, which necessitates that each codeword have an even number of bits. While there are (n C n/2) dc-free output codewords that can be formed from a sequence of n bits, an input binary bit stream of k bits can select only k=floor log.sub.2 (n C n/2) of them, resulting in a maximum code rate of k/n. To obtain a higher code rate, a larger sequence must be used, requiring a larger "codebook". For example, a dc-free code employing a 14-bit output codeword would determine that k=floor log.sub.2 (14 C 7)=11, thereby limiting the code rate to 11/14 and requiring a codebook of 2.sup.11 words. A slightly higher code rate of 13/16 would require a block length of 16 bits and a codebook of 2.sup.13 words.
In the co-pending application of co-inventor Emina Soljanin, Ser. No. 08/515,445 filed Aug. 15, 1995, an encoding method is disclosed which produces a dc-free code using a smaller codebook than would be predicted by the above equations. This is accomplished, in part, by eliminating the restriction that channel codewords must all have a block digital sum (BDS) of zero and contain only an even number of bits. Instead, codewords are formed of sets of concatenated subwords each of which may have an arbitrary BDS so long as the overall digital sum of the subwords is zero. For example, sets of pairs of subwords having complementary block digital sum may be used or there may be "j" subwords each of BDS=-1 and one subword of BDS="+j", etc. In one illustrative code, pairs of bipolar subwords having the same BDS, but of complementary sign were concatenated in an order determined by a p-bit portion of the length k input sequence. The remaining (k-p) bits of the length k input sequence are divided into q groups of m bits. Each of the q groups selects (from a storage unit) one of 2.sup.m bipolar length L subwords having a predetermined BDS. Since the m input bits are mapped to an output subword having L symbols, an "inner" rate m/L code is thereby defined. The number m is determined from floor log.sub.2 (L C n), where n is selected to provide a suitable number of dc-free combinations having a BDS=(L-2n). The overall code rate is, of course, established by the fact that k input bits produce qL output symbols, i.e, the rate is k/(qL), where k=p+qm.
Shown below is a table summarizing four of the illustrative codes. The columns are identified as follows: r is the code rate expressed as a fraction in which the numerator represents the number of input binary signals (identified as k in the second column), and the denominator represents the corresponding number of output symbols (represented by qL in the third column). q is the number of groups of m bits in the input and the number of groups of length L in the encoded output. The block digital sum of the subwords is indicated in the column BDS, while p/q identifies the outer code rate and m/L identifies the inner code rate. Note that in the rate 18/22 code there are pairs of subwords having block digital sums of .+-.1 as well as .+-.3. In the ensuing description of the present invention, reference will be made to the 46/56 code in the table below:
______________________________________ r k qL q L LCn m BDS qm p p/q m/L ______________________________________ 11/14 11 14 2 7 7C3 5 1 10 1 1/2 5/7 46/56 46 56 8 7 7C3 5 1 40 6 6/8 5/7 18/22 18 22 2 11 11C5 8 1 16 2 2/2 8/11 11C4 8 3 " " " " ______________________________________
In the above-mentioned co-pending application, the disclosure of which is hereby incorporated by reference, a method of decoding the encoded qL sequence is disclosed which assumes a noiseless channel. When the individual bipolar symbols of amplitude +1, -1 are applied to a noiseless (1-D) channel the channel transfer function causes the received sequence qL to have readily apparent amplitudes of +2, 0 or -2, exactly. However, when the encoded sequence is received from a noisy channel, the signals received may no longer have values that are exactly +2 or -2. The correct values of the symbol sequence must then be detected from the noisy samples received from the channel. This is accomplished most efficiently by establishing the most probable values of each of the qL symbols, having in mind the permissible values allowed by the coding scheme. Once these values have been established decoding may take place as described in the aforementioned co-pending application.
The detection of codes on a (1- D) channel may be accomplished by employing such known prior art techniques as the time-varying trellis detection method disclosed by L. Fredrickson, R. Karabed, J. W. Rae, P. H. Siegel, H. Thapar, and R. Wood, "Improved trellis coding for partial response channels," IEEE Trans. Magn., vol. 31, no. 2, pp. 1141-48, March 1995 or by concatenated detection described by K. J. Knudson, J. K. Wolf and L. B. Milstein, "A concatenated decoding scheme for (1-D) partial response with matched spectral-null decoding", Proc. 1993 IEEE Global Telecommun. Conf. (GLOBECOM '93), Houston, Tex., November 1993, pp. 1960-1964. In this latter article it is proposed to treat the decoding process in two stages in which the first stage utilizes a maximum likelihood sequence estimation (MLSE) detector for the uncoded (1-D) channel to estimate the binary input sequence, ignoring the code. The second stage is an error-event detector which improves the estimate by using the dc-free block code to detect and correct minimum distance error events. Correction of minimum distance error events is made possible by the fact that minimum distance error events for the uncoded (1-D) channel have power at DC. Since the dc-free code has no power at dc, a minimum distance error event is detected whenever power at dc is observed. The error event detector used the dc-free block constraint to detect and correct minimum distance error events. The dc-free block constraint has the same properties as the dc-free code but includes some of the dc-free words not employed in the code.
While the above-referenced decoding methods of L. Fredrickson et al and Knudson et al will successfully decode the coded sequences of the above-mentioned co-pending application, these decoding methods do not make use of information about the encoding structure and must therefore attempt to decode the entire codeword as an entity. For example, the method of Knudson et al, which proceeds to estimate the entire codeword sequence (ignoring the code) provides resulting estimates which may not actually be codewords, i.e., may not be dc-free codewords. The Knudson et al method computes the BDS for each estimated codeword and, upon detecting a codeword having a non-zero BDS, modifies the estimate by the most likely minimum distance error event so that the result will be a word with zero BDS. The complexity of the postprocessing lies in its search for the most likely minimum distance error event. Similar considerations affect the use of the Fredrickson et al time varying trellis detection.